二叉树的中序遍历

发表于 | 分类于 |
字数统计: 747 字 | 阅读时长 ≈ 3 分钟

题目描述：给定一个二叉树的根节点 root ，返回它的 中序 遍历。

示例 1：
img
输入：root = [1,null,2,3]
输出：[1,3,2]

示例 2：
输入：root = []
输出：[]

示例 3：
输入：root = [1]
输出：[1]

示例 4：
输入：root = [1,2]
输出：[2,1]

示例 5：
输入：root = [1,null,2]
输出：[1,2]

方法一：迭代

前序和中序遍历的迭代写法仅仅略有不同：

  • 前序遍历需要每次向左走之前就访问根结点
  • 而中序遍历先压栈，在出栈的时候才访问
1.gif 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
  public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if(root == null) return res;

    Deque<TreeNode> stack = new LinkedList<>();
    while(!stack.isEmpty() || root != null) {
      //先遍历左子树
      while(root != null) {
        stack.push(root);
        root = root.left;
      }
      //此时node的左节点为空，将node入res
      root = stack.pop();
      res.add(root.val);
      //然后再把node的right子节点赋给node，若有值,继续以上步骤
      root = root.right;
    }
    return res;
  }
}

var inorderTraversal = function(root) {
  let res = [], stack = []
  while(root || stack.length) {
    //先遍历左子树
    while(root) {
      stack.push(root)
      root = root.left
    }
    //此时root的左节点为空，将root入res
    root = stack.pop()
    res.push(root.val)
    //然后再把root的right子节点赋给root，若有值,继续以上步骤
    root = root.right
  }
  return res
};

复杂度分析

  • 时间复杂度：，其中 n 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。

  • 空间复杂度：O(n)。空间复杂度取决于栈深度，而栈深度在二叉树为一条链的情况下会达到 O(n) 的级别。

执行结果：通过

  • 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
  • 内存消耗：36.6 MB, 在所有 Java 提交中击败了69.15%的用户

方法二：递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
  public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<Integer>();
    inorder(root, res);
    return res;
  }

  public void inorder (TreeNode root, List<Integer> res) {
    if(root == null) return;
    inorder(root.left, res);
    res.add(root.val);
    inorder(root.right, res);
  }
}

var inorderTraversal = function(root) {
    let res = []
    inorder(root, res)
    return res
};
var inorder = function(root, res) {
    if(root === null) return
    inorder(root.left, res)
    res.push(root.val)
    inorder(root.right, res)
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。

  • 空间复杂度：O(n)。空间复杂度取决于递归的栈深度，而栈深度在二叉树为一条链的情况下会达到 O(n) 的级别。

执行结果：通过

  • 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

  • 内存消耗：36.6 MB, 在所有 Java 提交中击败了69.86%的用户